import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<List<String>> ret;
    List<String> path;
    boolean[][] dp;
    int n;


    public List<List<String>> partition(String s) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        n = s.length();
        dp = new boolean[n][n];

        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }
            }
        }

        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int pos) {
        if(pos == n){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int j = pos; j < n; ++j) {
            if (dp[pos][j]) {
                path.add(s.substring(pos, j + 1));
                dfs(s, j + 1);
                path.remove(path.size() - 1);
            }
        }

    }

}
